package com.algrithom.sort.bucket;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

import com.util.CommonUtil;

/**
 * 基数排序
 *
 * <p>
 * 基数排序：根据键值的每位数字来分配桶 计数排序：每个桶只存储单一键值 桶排序：每个桶存储一定范围的数值
 *
 * @author think
 * @version 1.0.0
 */
class BaseSort {
    
    private static final int VALUE_COUNT = 10;
    
    private static BaseSort instance = new BaseSort();
    
    static BaseSort getInstance(){
        if (Objects.isNull(instance)) {
            instance = new BaseSort();
        }
        return instance;
    }
    
    /**
     * 基数排序
     *
     * @param array 输入数组
     */
    void radixSort(Integer[] array){
        
        // 查找最大值
        int max = Arrays.stream(array).max((k1,k2) -> k1 > k2 ? 1 : k1.equals(k2) ? 0 : -1).orElse(0);
        
        // 关键字的个数，我们使用个位、十位、百位...当做关键字，所以关键字的个数就是最大值的位数
        int keysNum = String.valueOf(max).length();
        
        // 每位可能的数字为0~9，所以设置10个桶
        List<ArrayList<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < VALUE_COUNT; i++) {
            // 桶由ArrayList<Integer>构成
            buckets.add(new ArrayList<>());
        }
        
        // 由最次关键字开始，依次按照关键字进行分配
        for (int i = 0; i < keysNum; i++) {
            // 扫描所有数组元素，将元素分配到对应的桶中
            for (Integer integer : array) {
                // 取出该元素对应第i+1位上的数字，比如258，现在要取出十位上的数字，258%100=58,58/10=5
                int key = (integer % (int)Math.pow(10,i + 1)) / (int)Math.pow(10,i);
                // 将该元素放入关键字为key的桶中
                buckets.get(key).add(integer);
            }
            
            // 分配完之后，将桶中的元素依次复制回数组
            int counter = 0;
            // 元素计数器
            for (int j = 0; j < VALUE_COUNT; j++) {
                // 关键字为j的桶
                ArrayList<Integer> bucket = buckets.get(j);
                while (bucket.size() > 0) {
                    // 将桶中的第一个元素复制到数组，并移除
                    array[counter++] = bucket.remove(0);
                }
            }
            System.out.print("第" + (i + 1) + "轮排序：");
            CommonUtil.display(array);
        }
    }
}
